/*!
 * \file Graph.h
 * \brief A data structure representing a Simple Graph.
 *
 * \see Graphs
 *
 * \date Jun 18, 2012
 * \author correa
 */

#ifndef GRAPH_H_
#define GRAPH_H_

#include <cstdio>
#include <math.h>
#include "OrderedSet.h"
#include "OrderedBinaryRelation.h"
#include "ArrayOrderedSet.h"
#include "vEBTree.h"
#include "ArrayvEBTree.h"
#include "BitTools.h"


typedef enum GT { GT_GRAPH, GT_COMPLEMENT } graphType;//!< the type of the graph


/*!
 * \brief A Simple Graph with the vertices being natural numbers
 *
 * A Graph is a pair of a set of elements V and a binary relation E between then.
 * This class implements a simple graph, that is a graph where the relation E is simetric
 * and not reflexive, where the set V, the set of the vertices, is a set of natural
 * numbers.
 *
 * This class implements a simple undirected graph. As the set of vertexes are fixed to
 * be a subset of the natural numbers, the graph is completely defined by the number of
 * elements in V and the relation E, so the graph is a special type of binary relation.
 *
 * We use the natural order of "bigger than" as the order over the elements in the set V,
 * and the lexicographic order of the pairs as the order of the pairs of elements.
 */
template<class T >
class Graph : OrderedBinaryRelation<long> {

protected:

	long n;//!< The number of vertexes in the graph, the vertex are the natural numbers in the
	//interval [0, ..., n].

	T** adj;//!< The adjacent matrix of the graph. To each vertex i we associate
	// a orderedSet to represent the neighbours of the vertex.

	/*!
	 * \brief A simple constructor.
	 *
	 * A simple constructor used internally to allocate memory for a general object of this
	 * class.
	 *
	 */
	Graph() {};

public:

	/*!
	 * \brief The base constructor
	 *
	 * Create a simple graph with vertex set {0,1,...n} and a empty edge set. The set of edges
	 * is represented by a adjacent matrix, in this matrix each line is a OrderedSet. The second
	 * argument of this function is used to create the lines of the matrix according a specific
	 * implementation.
	 *
	 * Notice that this implementation of graph is completely independent of the data structure
	 * used to implement the adjacent matrix.
	 *
	 * \param n the number of elements in the vertex set
	 * \param factory a abstract factory to a OrderedSet<long>
	 *
	 * \see OrderedSet
	 * */
	Graph(long n, OrderedSetFactory<long>* factory);

	/*!
	 * \brief The base constructor
	 *
	 * Create a simple graph with vertex set {0,1,...n} and a empty edge set. The set of edges
	 * is represented by a adjacent matrix, in this matrix each line is a OrderedSet. The second
	 * argument of this function is used to create the lines of the matrix according a specific
	 * implementation.
	 *
	 * Notice that this implementation of graph is completely independent of the data structure
	 * used to implement the adjacent matrix.
	 *
	 * \param n the number of elements in the vertex set
	 * \param handle a pointer to store the information that will be used by the OrderedSetFactory
	 * \param factory a abstract factory to a OrderedSet<long>
	 *
	 * \see OrderedSet
	 * */
	Graph(long n, OrderedSetFactory<long>* factory, void* handle);

	/*!
	 * \brief The base constructor
	 *
	 * Create a simple graph with vertex set {0,1,...n} and a empty edge set. The set of edges
	 * is represented by a adjacent matrix, in this matrix each line is a OrderedSet. The second
	 * argument of this function is used to create the lines of the matrix according a specific
	 * implementation.
	 *
	 * Notice that this implementation of graph is completely independent of the data structure
	 * used to implement the adjacent matrix.
	 *
	 * \param n the number of elements in the vertex set
	 * \param handle a pointer to store the information that will be used by the OrderedSetFactory
	 * \param factory a abstract factory to a OrderedSet<long>
	 *
	 * \see OrderedSet
	 * */
	Graph(long n, OrderedSetFactory<long>* factory, void** handle);

	/*!
	 * \brief The destructor
	 *
	 * Clean all the information used by a object of this class
	 *
	 * */
	virtual ~Graph();

	/*!
	 * \brief The number of vertexes
	 *
	 * Return the cardinality of the vertex set.
	 *
	 * \return the number of vertexes in the graph
	 * */
	virtual long nverts();

	/*!
	 * \brief The number of edges
	 *
	 * Returns the cardinality of the edge set. It is implemented by a call to CardOfSet() in
	 * each line of the adjacency matrix and summing the results.
	 *
	 * \return the number of edges
	 * */
	virtual long long nedges();

	/*!
	 * \brief Add an edge between the two specified vertexes.
	 *
	 * Look at the adjacency matrix and add the element i to the set correspondent
	 * to the neighbours of j and the element j to the neighbours of i.
	 *
	 * If one of the specified elements is out of the universe an error will occur.
	 *
	 * \param i the first specified object.
	 * \param j the second specified object.
	 *
	 * \return true if it sucessed in add the edge ij to the graph, otherwise returns false.
	 * */
	virtual bool addEdge(long i, long j);

	/*!
	 * \brief Remove an edge between the two specified vertexes.
	 *
	 * Look at the adjacency matrix and remove the element i to the set correspondent
	 * to the neighbours of j and the element j to the neighbours of i.
	 *
	 * If one of the specified elements is out of the universe an error will occur.
	 *
	 * \param i the first specified object.
	 * \param j the second specified object.
	 *
	 * \return true if it sucessed in remove the edge ij to the graph, otherwise returns false.
	 * */
	virtual bool delEdge(long i, long j);

	/*!
	 * \brief Add all the edges possible in the graph.
	 *
	 * It has the same result as call allToSet() in each set used to store
	 * the adjacency matrix.
	 *
	 * It will transform the graph in a complete graph.
	 *
	 * */
	virtual void addAllEdges();

	/*!
	 * \brief Remove all the edges possible in the graph.
	 *
	 * It has the same result as call allToCompl() in each set used to store
	 * the adjacency matrix.
	 *
	 * It will transform the graph in a empty graph.
	 *
	 * */
	virtual void delAllEdges();

	/*!
	 * \brief Verify if there is an edge between the two specified vertexes.
	 *
	 * Look at the adjacency matrix and verify if i is neighbour of j.
	 *
	 * If one of the specified elements is out of the universe an error will occur.
	 *
	 * \param i the first specified object.
	 * \param j the second specified object.
	 *
	 * \return true if the edge ij is in the edge set, otherwise returns false.
	 * */
	virtual bool hasEdge(long i, long j);

	/*!
	 * \brief Return the i-th element of the universe.
	 *
	 * Return the element that is in the position i according to the order
	 * given to elements in the universe. Usually this value is the position
	 * itself, but we can reorganize the elements in the vertex set according
	 * other order, as in a homorphism.
	 *
	 * If the position is bigger than the number of elements in the universe, an
	 * error will occur.
	 *
	 * \param i the specified position.
	 *
	 * \return the element in the position i according to the order given to
	 * the elements in the vertex set.
	 *
	 * */
	virtual long vertex(long i);

	/*!
	 * \brief The number of neighbours of a specified vertex.
	 *
	 * Count the number of neighbours of a specified vertex. It is implemented using
	 * the function cardOfSet() for the OrderedSet.
	 *
	 * If the element is out of the universe, an error will occur.
	 *
	 * \param i the specified vertex.
	 *
	 * \return the number of neighbours of the specified vertex.
	 * */
	virtual long degree(long i);

	/*!
	 * \brief The number of anti-neighbours of a specified vertex.
	 *
	 * Count the number of anti-neighbours of a specified vertex. It is implemented using
	 * the function cardOfCompl() for the OrderedSet.
	 *
	 * If the element is out of the universe, an error will occur.
	 *
	 * \param i the specified vertex.
	 *
	 * \return the number of anti-neighbours of the specified vertex.
	 * */
	virtual long antidegree(long i);

	/*!
	 * \brief Retrieve the neighbourhood of a specified vertex as an OrderedSet.
	 *
	 * Retrieve neighbourhood of a specified vertex as an OrderedSet. If the
	 * specified element is out of the universe an error will occur.
	 *
	 * \param i the specified vertex.
	 *
	 * \return neighbourhood of a specified vertex as an OrderedSet.
	 * */
	virtual T* neig(long i);

	/*!
	 * \brief Retrieve the neighbourhood of a specified vertex as an array.
	 *
	 * Retrieve neighbourhood of a specified vertex as an array. A pointer to the
	 * array must be passed as parameter and the array must be at least the degree of
	 * i positions. The number of elements stored in the array is returned.
	 *
	 * If the specified element is out of the universe an error will occur. The same
	 * happens if the array passed as parameter has less than degree of i positions.
	 *
	 * \param i the specified vertex.
	 * \param neg a array to store the vertexes adjacent to the specified one.
	 *
	 * \return the degree of the vertex i.
	 * */
	virtual long neigToArray(long i, long* neg);

	/*!
	 * \brief Retrieve the neighbourhood of a specified vertex as a bit array .
	 *
	 * Retrieve neighbourhood of a specified vertex as a OrderedSet. If the
	 * specified element is out of the universe an error will occur.
	 *
	 * \param i the specified vertex.
	 *
	 * \return neighbourhood of a specified vertex as a OrderedSet.
	 * */
	virtual long* neigToBitArray(long i);

	/*!
	 * \brief Join the neigbourhood of j to the neigbourhood of i.
	 *
	 * Add all the neighbours of the second specified element to the neighbourhood of the
	 * first specified vertex. It is implemented using the method setUnionSet() of the
	 * class OrderedSet. The result overwrite the neigbourhood of the first element.
	 *
	 * If one of the elements is out of the universe, an error will occur.
	 *
	 * \param i the first specified element.
	 *
	 * \param j the second specified element.
	 *
	 * \see setUnionSet
	 * */
	virtual void joinAdj(long i, long j);

	/*!
	 * \brief Join the neigbourhood of j to the neigbourhood of i and store the result in the
	 * OrderedSet passed as parameter.
	 *
	 * Add all the neighbours of the second specified element to the neighbourhood of the
	 * first specified vertex. It is implemented using the method setUnionSet() of the
	 * class OrderedSet.
	 *
	 * This method do not chage tha neigbourhood of i or j.
	 *
	 * If one of the elements is out of the universe, an error will occur.
	 *
	 * \param i the first specified element.
	 *
	 * \param j the second specified element.
	 *
	 * \see setUnionSet
	 * */
	virtual void joinAdj(long i, long j, T* join);

	/*!
	 * \brief Calculate the commum neigbourhood of j and i.
	 *
	 * Determine the set of vertex that are neigbours of i and j at the
	 * same time. The result overwrite the neigbourhood of the first element.
	 * It is implemented using the method setIntersecSet() of the
	 * class OrderedSet.
	 *
	 * If one of the elements is out of the universe, an error will occur.
	 *
	 * \param i the first specified element.
	 *
	 * \param j the second specified element.
	 *
	 * \see setIntersecSet
	 * */
	virtual void comumAdj(long i, long j);

	/*!
	 * \brief Calculate the commum neigbourhood of j and i and store the result in the OrderedSet
	 * passed as parameter.
	 *
	 * Determine the set of vertex that are neigbours of i and j at the
	 * same time. It is implemented using the method setIntersecSet() of the
	 * class OrderedSet.
	 *
	 * If one of the elements is out of the universe, an error will occur.
	 *
	 * This method do not chage tha neigbourhood of i or j.
	 *
	 * \param i the first specified element.
	 *
	 * \param j the second specified element.
	 *
	 * \see setIntersecSet
	 * */
	virtual void comumAdj(long i, long j, T* comum);

	/*!
	 * \brief Remove from the neigbourhood of i to the neigbourhood of j.
	 *
	 * Remove all the neighbours of the second specified element to the neighbourhood of the
	 * first specified vertex. It is implemented using the method setDiffSet() of the
	 * class OrderedSet. The result overwrite the neigbourhood of the first element.
	 *
	 * If one of the elements is out of the universe, an error will occur.
	 *
	 * \param i the first specified element.
	 *
	 * \param j the second specified element.
	 *
	 * \see setDiffSet
	 * */
	virtual void difAdj(long i, long j);

	/*!
	 * \brief Remove the neigbourhood of j to the neigbourhood of i, but not overwrite
	 * the neighbourhood of i or j.
	 *
	 * remove all the neighbours of the second specified element to the neighbourhood of the
	 * first specified vertex. It is implemented using the method setDiffSet() of the
	 * class OrderedSet.
	 *
	 * If one of the elements is out of the universe, an error will occur.
	 *
	 * This method do not chage tha neigbourhood of i or j.
	 *
	 * \param i the first specified element.
	 *
	 * \param j the second specified element.
	 *
	 * \see setDiffSet
	 * */
	virtual void difAdj(long i, long j, T* dif);

	/*!
	 * \brief Create a clone of the current graph.
	 *
	 * Create a clone of the current graph, with the same number of edges, the same
	 * vertex set and the same edges. It is implemented using the method clone
	 * to each line of the adjacency matrix.
	 *
	 * \return a copy of the current graph.
	 * */
	virtual OrderedSet<OrderedPair<long> >* clone();

	/*!
	 * \brief Create a homomorphism of the current graph
	 *
	 * A homomorphism of a graph is a labeling function *l* of its vertex such that if ij is a edge
	 * than l(i)l(j) is an edge and is ij is not an edge than ij is not an edge.
	 *
	 * The array passed as parameter is the labeling function, the position i represents the new
	 * label of the vertex i. the long is the size of the array.
	 *
	 * Notice that is not necessary that the array has a position to every vertex, and you can
	 * associate more than one vertex to a same label. But it can cause bad behaive of the functions.
	 *
	 * \param rsize the size of the array R
	 *
	 * \param R the labeling function, each position represents the new label of the vertex in that
	 * position.
	 *
	 * \return A homomorphism of the current graph represented by R as the labeling function.
	 *
	 * */
	virtual Graph* homomorphism(long rsize, long* R);

	/*!
	 * \brief The complement of the current graph.
	 *
	 * The complement of a graph is another graph that has the same set of vertexes but the set of
	 * edges is different. If uv is an edge in the graph if is not in the complement, if is not an edge
	 * in the graph is in the complement, except for the edges in the form vv.
	 *
	 *
	 * \return the complement of the current graph.
	 * */
	virtual Graph* complement();

	/*!
	 * \brief Create the square of the current graph.
	 *
	 * The square of a graph *G* is a graph with the same set of vertex and all the edges
	 * in the egdes of *G* and the edges *uv* such that exists in G the edges *uw* and
	 * *vw* for some vertex w in the vertex set.
	 *
	 * \return the square graph of the current graph.
	 * */
	virtual Graph* square();


	/*!
	 * \brief Add an edge between the specifieds vertexes.
	 *
	 * The same as addEdge(i,j)
	 *
	 * \param i the first especified vertex.
	 * \param j the second especified vertex.
	 *
	 * \return true if it sucessed in add the edge, and false otherwise.
	 *
	 *\see addEdge()
	 * */
	bool add(long i, long j);

	/*!
	 * \brief Remove the edge between the two specified vertexes.
	 *
	 * The same as removeEdege().
	 *
	 * \param i the first specified vertex.
	 * \param j the second specified vertex.
	 *
	 * \return true if sucessed in remove the edge and false otherwise.
	 *
	 * \see removeEdge().
	 * */
	bool remove(long i, long j);

	/*!
	 * \brief Retrieve the neighbourhood of the specified vertex.
	 *
	 * The same as neigh(elem).
	 *
	 * \param elem the specified vertex.
	 *
	 * \return the neigbourhood of the specified vertex.
	 *
	 * \see neigh()
	 * */
	virtual OrderedSet<long>* image(long elem);

	/*!
	 * \brief Retrieve the neighbourhood of the specified vertex.
	 *
	 * The same as neigh(elem).
	 *
	 * \param elem the specified vertex.
	 *
	 * \return the neigbourhood of the specified vertex.
	 *
	 * \see neigh()
	 * */
	virtual OrderedSet<long>* inverse(long elem);

	/*!
	 * \brief Determine wherever or not the relation over the graph is transitive.
	 *
	 * \return false, since by definition a graph is not transitive.
	 * */
	virtual bool isTransitive();

	/*!
	 * \brief Determine wherever or not the relation over the graph is reflexive.
	 *
	 * \return false, since by definition a graph is not reflexive.
	 * */
	virtual bool isReflexive();

	/*!
	 * \brief Determine wherever or not the relation over the graph is empty.
	 *
	 * A graph is considered empty, if its edge set is empty.
	 *
	 * \return true if the current graph has no edges, and false otherwise.
	 * */
	virtual bool isEmpty();

	/*!
	 * \brief Determine wherever or not the relation over the graph is simetric.
	 *
	 * \return true, since by definition a graph is not simetric.
	 * */
	virtual bool isSimetric();

	/*!
	 * \brief Determine wherever or not the relation over the graph is anti-simetric.
	 *
	 * \return false, since by definition a graph is not anti-simetric.
	 * */
	virtual bool isAntiSimetric();

	/*!
	 * \brief The cardinality of the neigbourhood of the specified vertex.
	 *
	 * \param elem the specified vertex.
	 *
	 * \return the numbers of neighbours of the specified vertex.
	 * */
	virtual long degreeIn(long elem);

	/*!
	 * \brief The cardinality of the neigbourhood of the specified vertex.
	 *
	 * \param elem the specified vertex.
	 *
	 * \return the numbers of neighbours of the specified vertex.
	 * */
	virtual long degreeOut(long elem);

	/*!
	 * \brief A iterator to the edge set of the current graph.
	 *
	 * A iterator to the edge set of the current graph. The edges are represented as
	 * an OrderedPair.
	 *
	 * \return A iterator to the edge set of the current graph.
	 */
	virtual OrderedSet<OrderedPair<long> >::Iterator* newSetIterator();

	/*!
	 * \brief A iterator to the edge set of the current graph with a filter.
	 *
	 * A iterator to the edge set of the current graph. The edges are represented as
	 * an OrderedPair. The filter eliminate same of the edges of the graph.
	 *
	 * \param filter the specified filter.
	 *
	 * \return A iterator to the edge set of the current graph.
	 */
	virtual OrderedSet<OrderedPair<long> >::Iterator* newSetIterator(OrderedSet<OrderedPair<long> >* filter);

	/*!
	 * \brief A iterator to the edge set of the complement of the current graph.
	 *
	 * A iterator to the edge set of the complement the current graph. The edges are represented as
	 * an OrderedPair.
	 *
	 * \return A iterator to the edge set of the current graph.
	 */
	virtual OrderedSet<OrderedPair<long> >::Iterator* newComplIterator();

	/*!
	 * \brief A iterator to the edge set of the complement of the current graph with a filter.
	 *
	 * A iterator to the edge set of the complement of the current graph. The edges are represented as
	 * an OrderedPair. The filter eliminate same of the edges of the complement.
	 *
	 * \param filter the specified filter.
	 *
	 * \return A iterator to the edge set of the complement of the current graph.
	 */
	virtual OrderedSet<OrderedPair<long> >::Iterator* newComplIterator(OrderedSet<OrderedPair<long> >* filter);


	/*!
	 * \brief The smallest edge lexicographic bigger than the edge i that is in the graph.
	 *
	 * This method is necessary due the inhrent from OrderedSet.
	 *
	 * \param i the specified edge.
	 *
	 * \return The smallest edge lexicographic bigger than the edge i that is in the graph.
	 */
	virtual OrderedPair<long> nextSetElement(OrderedPair<long>  i);

	/*!
	 * \brief The smallest edge lexicographic bigger than the edge i that is in the complement of the graph.
	 *
	 * This method is necessary due the inhrent from OrderedSet.
	 *
	 * \param i the specified edge.
	 *
	 * \return The smallest edge lexicographic bigger than the edge i that is in the complement of the graph.
	 */
	virtual OrderedPair<long> nextComplElement(OrderedPair<long> i);

	/*!
	 * \brief Add the edge represented by the specified pair to the graph
	 *
	 * The same as addEdge(i.getX(), i.getY())
	 *
	 * \param i the specified pair
	 *
	 * \see addEdge()
	 */
	virtual void toSet(OrderedPair<long>  i);

	/*!
	 * \brief Remove the edge represented by the specified pair to the graph
	 *
	 * The same as removeEdge(i.getX(), i.getY())
	 *
	 * \param i the specified pair
	 *
	 * \see removeEdge()
	 */
	virtual void toCompl(OrderedPair<long> i);

	/*!
	 * \brief Swap the edge represented by the specified ordered pair.
	 *
	 * If the edge represented by the specified ordered pair is in the graph,
	 * it will be removed if not it will be added.
	 *
	 * \param i the specified ordered pair.
	 *
	 */
	virtual void swapElement(OrderedPair<long> i);

	/*!
	 * \brief Verify if the edge represented by the specified ordered pair is in the
	 * edge set.
	 *
	 * The same as hasEdge(i.getX(), i.getY()).
	 *
	 * \param i the specified edge
	 *
	 * \return true if the edge is in the edge set and false otherwise.
	 *
	 * \see hasEdge()
	 */
	virtual bool isInSet(OrderedPair<long> i);

	/*!
	 * \brief Verify if the edge represented by the specified ordered pair is not in the
	 * edge set.
	 *
	 * The same as (!hasEdge(i.getX(), i.getY())).
	 *
	 * \param i the specified edge
	 *
	 * \return true if the edge is not in the edge set and false otherwise.
	 *
	 * \see hasEdge()
	 */
	virtual bool isInCompl(OrderedPair<long> i);

	/*!
	 * \brief Retrieve the edge set of the current graph as an array.
	 *
	 * Retrive the edge set of the current graph as an array of OrderedPair.
	 *
	 * \param size a pointer to store the size of the vector returned.
	 *
	 * \return a array with the edge set of the current graph.
	 */
	virtual OrderedPair<long>* toArray(long* size);

	/*!
	 * \brief The number of vertexes.
	 *
	 * The number of vertexes in the vertex set.
	 *
	 * \return the number of vertexes.
	 */
	virtual long size();

	/*!
	 * \brief Add all edges to the graph.
	 *
	 * The same as addAllEdges().
	 *
	 * \see addAllEdges().
	 */
	virtual void allToSet();

	/*!
	 * \brief remove all edges to the graph.
	 *
	 * The same as removeAllEdges().
	 *
	 * \see removeAllEdges().
	 *
	 */
	virtual void allToCompl();

	/*!
	 * \brief The first edge in the edge set
	 *
	 * The first edge in the edge set, according to the order impose over
	 * all edges.
	 *
	 * \return the first edge in the edge set, according to the order impose over
	 * all edges.
	 */
	virtual OrderedPair<long> firstInSet();

	/*!
	 * \brief The first edge not in the edge set
	 *
	 * The first edge not in the edge set, according to the order impose over
	 * all edges.
	 *
	 * \return the first edge not in the edge set, according to the order impose over
	 * all edges.
	 */
	virtual OrderedPair<long> firstInCompl();

	/*!
	 * \brief The cardinality of the edge set.
	 *
	 * The same as nedges().
	 *
	 * \return the umber of edges in the graph.
	 *
	 * \see nedges().
	 */
	virtual long cardOfSet();

	/*!
	 * \brief The cardinality of the edge set of the complement
	 *
	 * The same as nedges() in the complement graph of the current graph.
	 *
	 * \return the umber of edges in the graph.
	 *
	 * \see nedges().
	 */	virtual long cardOfCompl();

	/*!
	 * \brief Transform the current Graph in its complement.
	 *
	 * The same as complement().
	 *
	 * \see complement().
	 */
	virtual void setComplement();

	/*!
	 * \brief Create the complement of the current graph and store in the
	 * OrderedSet passed as parameter.
	 *
	 * the same as complement(), but not overwrite the information on the current
	 * object. The result is stored in a pointer passed as parameter.
	 *
	 * \param res a pointer to store the complement of the current graph.
	 */
	virtual void setComplement(OrderedSet<OrderedPair<long> > * res);

	//DEBUG
	virtual void show();
};

template<class T>
inline Graph<T>::Graph(long n, OrderedSetFactory<long>* factory){
	this->n = n;
	//allocate memory to the adj list
	this->adj = new T*[n];
	for(long i = 0; i < n; i++){
		adj[i] = (T*)factory->newOrderedSet(n);
	}
}

template<class T>
inline Graph<T>::Graph(long n, OrderedSetFactory<long>* factory, void* handle){
	this->n = n;
	//allocate memory to the adj list
	this->adj = new T*[n];
	for(long i = 0; i < n; i++){
		adj[i] = (T*)factory->newOrderedSet(n, handle);
	}
}

template<class T>
inline Graph<T>::Graph(long n, OrderedSetFactory<long>* factory, void** handle){
	this->n = n;
	//alocate memory to the adj list
	this->adj = new T*[n];
	for(long i = 0; i < n; i++){
		adj[i] = factory->newOrderedSet(n, handle[i]);
	}
}

template<class T>
inline Graph<T>::~Graph(){
	//delete the adj list
	for(long i = 0; i < n; i++){
		delete adj[i];
	}
}

template<class T>
inline long Graph<T>::nverts(){
	return n;
}

template<class T>
inline long long Graph<T>::nedges(){
	long count = 0;

	//sum over all vertexes
	for(long i = 0; i < n; i++){
		count += adj[i]->cardOfSet();
	}
	return count >> 1;
}

template<class T>
inline bool Graph<T>::addEdge(long i, long j){
	adj[j]->toSet(i);
	adj[i]->toSet(j);
	return true;
}

template<class T>
inline bool Graph<T>::delEdge(long i, long j){
	adj[i]->toCompl(j);
	adj[j]->toCompl(i);
	return true;
}

template<class T>
inline void Graph<T>::addAllEdges(){
	for(long i = 0; i < n; i++){
		adj[i]->allToSet();
	}
}

template<class T>
inline void Graph<T>::delAllEdges(){
	for(long i = 0; i < n; i++){
		adj[i]->allToCompl();
	}
}

template<class T>
inline bool Graph<T>::hasEdge(long i, long j){
	return adj[i]->isInSet(j);
}

template<class T>
inline long Graph<T>::vertex(long i){
	return i;
}

template<class T>
inline long Graph<T>::degree(long i){
	return adj[i]->cardOfSet();
}

template<class T>
inline long Graph<T>::antidegree(long i){
	return n - adj[i]->cardOfSet() - 1;
}

template<class T>
inline T* Graph<T>::neig(long i){
	return (T*)adj[i]->clone();
}

template<class T>
inline void Graph<T>::joinAdj(long i, long j){
	adj[i]->setUnionSet(adj[j]);
}

template<class T>
inline void Graph<T>::joinAdj(long i, long j, T* join){
	adj[i]->setUnionSet(adj[j], join);
}

template<class T>
inline void Graph<T>::comumAdj(long i, long j){
	adj[i]->setIntersecSet(adj[j]);
}

template<class T>
inline void Graph<T>::comumAdj(long i, long j, T* comum){
	adj[i]->setIntersecSet(adj[j], comum);
}

template<class T>
inline void Graph<T>::difAdj(long i, long j){
	adj[i]->setDiffSet(adj[j]);
}

template<class T>
inline void Graph<T>::difAdj(long i, long j, T* dif){
	adj[i]->setDiffSet(adj[j], dif);
}

template<class T>
inline OrderedSet<OrderedPair<long> >* Graph<T>::clone(){
	Graph<T>* g = (Graph<T>*)malloc(sizeof(Graph<T>));
	g->n = n;

	//clone all lines
	for(long i = 0; i < n; i++)	g->adj[i] = (T*)adj[i]->clone();
	return (OrderedSet<OrderedPair<long> >*)g;
}

template<class T>
inline Graph<T>* Graph<T>::square(){
	//clone the current graph
	Graph<T>* g = (Graph<T>*)clone();

	//add the transitive edges
	for(long i = 0; i < n; i++){
		for(long j = i+1; j < n; j++ ){
			if(hasEdge(i,j)){
				g->adj[j]->setUnionSet(adj[i]);
				g->adj[i]->setUnionSet(adj[j]);
			}
		}
	}
	return g;
}

template<class T>
inline long Graph<T>::neigToArray(long i, long* neg){
	OrderedSet<long>::Iterator* it = adj[i]->newSetIterator();
	long j = 0;
	while(it->hasNext()){
		neg[j++] = it->next();
	}
	return j;
}

template<class T>
inline long* Graph<T>::neigToBitArray(long i){
	long size;
	return adj[i]->toArray(&size);
}


template<class T>
inline Graph<T>* Graph<T>::homomorphism(long rsize, long* R){

	//inner class to represented the homomophism
	class HGraph : Graph<T>{
		private:
			long* vR;
			long* Rv;
		public:
			// contructor
			HGraph(Graph<T>* g, long a, long* A){
				n = g->n;
				adj = new T*[n];
				vR = new long[n];
				Rv = new long[n];
				for(long i = 0; i < n; i++){
					adj[i] = (T*)g->adj[i]->clone();
					vR[A[i]] = i;
					Rv[i] = A[i];
				}
			}

			~HGraph(){
				delete vR;
				delete Rv;
				for(long i = 0; i < n; i++){
					delete adj[i];
				}
				delete adj;
			}

			//clone
			OrderedSet<OrderedPair<long> >* clone(){
				HGraph* hg;
				hg->n = n;
				hg->adj = new T*[n];
				vR = new long[n];
				Rv = new long[n];
				for(long i = 0; i < n; i++){
					hg->adj[i] = (T*)adj[i]->clone();
					hg->vR[i] = vR[i];
					hg->Rv[i] = Rv[i];
				}
				return (OrderedSet<OrderedPair<long> >*)hg;
			}

			//add an edges
			bool addEdge(long i, long j){
				Graph<T>::addEdge(vR[i], vR[j]);
			}

			//delete an adge
			bool delEdge(long i, long j){
				Graph<T>::delEdge(vR[i], vR[j]);
			}

			//verify if there is a edge between i and j
			bool hasEdge(long i, long j){
				Graph<T>::hasEdge(vR[i], vR[j]);
			}

			long vertex(long i){
				return Rv[i];
			}

		};
	Graph<T>* g = (Graph<T>*)new HGraph(this, rsize, R);
	return g;
}


template<class T>
inline Graph<T>* Graph<T>::complement(){
	Graph<T>* g = (Graph<T>*)clone();
	for(long i = 0; i < n; i++)g->adj[i]->setComplement();
	return g;
}

template<class T>
inline bool Graph<T>::add(long i, long j){
	return addEdge(i,j);
}


template<class T>
inline bool Graph<T>::remove(long i, long j){
	return delEdge(i,j);
}


template<class T>
inline OrderedSet<long>* Graph<T>::image(long elem){
	return adj[elem]->clone();
}

template<class T>
inline OrderedSet<long>* Graph<T>::inverse(long elem){
	return adj[elem]->clone();
}


template<class T>
inline bool Graph<T>::isTransitive(){
	return false;
}


template<class T>
inline bool Graph<T>::isReflexive(){
	return false;
}


template<class T>
inline bool Graph<T>::isEmpty(){
	bool empty = true;
	//a empty graph has no edges
	for(long i = 0; i < n; i++){
		if(!adj[i]->isEmpty()) empty = false;
	}
	return empty;
}

template<class T>
inline bool Graph<T>::isSimetric(){
	return true;
}


template<class T>
inline bool Graph<T>::isAntiSimetric(){
	return false;
}


template<class T>
inline long Graph<T>::degreeIn(long elem){
	return degree(elem);
}


template<class T>
inline long Graph<T>::degreeOut(long elem){
	return degree(elem);
}

template<class T>
inline OrderedSet<OrderedPair<long> >::Iterator* Graph<T>::newSetIterator(){
	//simple iterator to the edges as ordered pair
	class Iterator :public OrderedSet<OrderedPair<long> >::Iterator{
		friend class Graph<T>;
		private:
			Graph<T>* g;
			long i;
			long j;

		public :
			Iterator(Graph<T>* h){
				g = h;
			}

			~Iterator(){};

			void start(){
				long l = g->n+1;
				long k = 0;
				while(l >= g->n && k < g->n){
					l = g->adj[k++]->firstInSet();
				}
				if(l < g->n && k < g->n){
					i = k;
					j = l;
				}
				else i = j = -1;
			}

			void restart(){
				start();
			}

			void restartFrom(OrderedPair<long> x){
				i = x.getX();
				j = x.getY();
				next();
			}

			bool hasNext(){
				return (i != -1) && (j != -1);
			}

			OrderedPair<long> next(){
				long k = i;
				long l = j;
				j = g->adj[i]->nextSetElement(j+1);
				if(j >= g->n){
					while(j >= g->n && i < g->n){
						j = g->adj[i++]->firstInSet();
					}
					if(j >= g->n || i >= g->n)i = j = -1;
				}
				return OrderedPair<long>(k, l);
			}
	};
	return new Iterator(this);
}

template<class T>
inline OrderedSet<OrderedPair<long> >::Iterator* Graph<T>::newSetIterator(OrderedSet<OrderedPair<long> >* filter){
	class Iterator :public OrderedSet<OrderedPair<long> >::Iterator{
		friend class Graph<T>;
		private:
			Graph<T>* g;
			long i;
			long j;
			OrderedSet<OrderedPair<long> >* filter;

		public :
			Iterator(Graph<T>* h, OrderedSet<OrderedPair<long> >* filter){
				g = h;
				this->filter = filter;
			}

			~Iterator(){};

			void start(){
				long l = g->n+1;
				long k = 0;
				OrderedPair<long>* pair = new OrderedPair<long>(l,k);
				while(l >= g->n && k < g->n && filter->isInCompl(*pair)){
					l = g->adj[k++]->firstInSet();
					delete pair;
					pair = new OrderedPair<long>(l,k);
				}
				if(l < g->n && k < g->n){
					i = k;
					j = l;
				}
				else i = j = -1;
			}

			void restart(){
				start();
			}

			void restartFrom(OrderedPair<long> x){
				i = x.getX();
				j = x.getY();
				next();
			}

			bool hasNext(){
				return (i != -1) && (j != -1);
			}

			OrderedPair<long> next(){
				long k = i;
				long l = j;
				OrderedPair<long>* pair = new OrderedPair<long>(i,j);
				while(i >= g->n && k < g->n && filter->isInCompl(*pair)){
					j = g->adj[i++]->firstInSet();
					delete pair;
					pair = new OrderedPair<long>(i,j);
				}
				if(l < g->n && k < g->n){
					i = k;
					j = l;
				}
				else i = j = -1;
				return OrderedPair<long>(k, l);
			}
	};
	return new Iterator(this, filter);
}

template<class T>
inline OrderedSet<OrderedPair<long> >::Iterator* Graph<T>::newComplIterator(){
	class Iterator : public OrderedSet<OrderedPair<long> >::Iterator{
		friend class Graph<T>;
		private:
			Graph<T>* g;
			long i;
			long j;

		public :
			Iterator(Graph<T>* h){
				g = h;
			}

			~Iterator(){};

			void start(){
				long l = g->n+1;
				long k = 0;
				while(l >= g->n && k < g->n){
					l = g->adj[k++]->firstInCompl();
				}
				if(l < g->n && k < g->n){
					i = k;
					j = l;
				}
				else i = j = -1;
			}

			void restart(){
				start();
			}

			void restartFrom(OrderedPair<long> x){
				i = x.getX();
				j = x.getY();
				next();
			}

			bool hasNext(){
				return (i != -1) && (j != -1);
			}

			OrderedPair<long> next(){
				long k = i;
				long l = j;
				j = g->adj[i]->nextComplElement(j+1);
				if(j >= g->n){
					while(j >= g->n && i < g->n){
						j = g->adj[i++]->firstInCompl();
					}
					if(j >= g->n || i >= g->n)i = j = -1;
				}
				return OrderedPair<long>(k,l);
			}
	};
	return new Iterator(this);
}

template<class T>
inline OrderedSet<OrderedPair<long> >::Iterator* Graph<T>::newComplIterator(OrderedSet<OrderedPair<long> >* filter){
	class Iterator :public OrderedSet<OrderedPair<long> >::Iterator{
		friend class Graph<T>;
		private:
			Graph<T>* g;
			long i;
			long j;
			OrderedSet<OrderedPair<long> >* filter;

		public :
			Iterator(Graph* h, OrderedSet<OrderedPair<long> >* filter){
				g = h;
				this->filter = filter;
			}

			~Iterator(){};

			void start(){
				long l = g->n+1;
				long k = 0;
				OrderedPair<long>* pair = new OrderedPair<long>(l,k);
				while(l >= g->n && k < g->n && filter->isInSet(*pair)){
					l = g->adj[k++]->firstInCompl();
					delete pair;
					pair = new OrderedPair<long>(l,k);
				}
				if(l < g->n && k < g->n){
					i = k;
					j = l;
				}
				else i = j = -1;
			}

			void restart(){
				start();
			}

			void restartFrom(OrderedPair<long> x){
				i = x.getX();
				j = x.getY();
				next();
			}

			bool hasNext(){
				return (i != -1) && (j != -1);
			}

			OrderedPair<long> next(){
				long k = i;
				long l = j;
				OrderedPair<long>* pair = new OrderedPair<long>(i,j);
				while(i >= g->n && k < g->n && filter->isInSet(*pair)){
					j = g->adj[i++]->firstInCompl();
					delete pair;
					pair = new OrderedPair<long>(i,j);
				}
				if(l < g->n && k < g->n){
					i = k;
					j = l;
				}
				else i = j = -1;
				return OrderedPair<long>(k, l);
			}
	};
	return new Iterator(this, filter);
}

template<class T>
inline OrderedPair<long> Graph<T>::nextSetElement(OrderedPair<long> i){
	OrderedPair<long> pair(0,0);
	long x = i.getX();
	long y = adj[x]->nextSetElement(i.getY() + 1);
	while(y >= n){
		x++;
		y = adj[x]->nextSetElement(0);
	}
	pair.setX(x);
	pair.setY(y);
	return pair;
}

template<class T>
inline OrderedPair<long> Graph<T>::nextComplElement(OrderedPair<long> i){
	OrderedPair<long> pair(0,0);
	long x = i.getX();
	long y = adj[x]->nextComplElement(i.getY() + 1);
	while(y >= n){
		x++;
		y = adj[x]->nextComplElement(0);
	}
	pair.setX(x);
	pair.setY(y);
	return pair;
}

template<class T>
inline void Graph<T>::toSet(OrderedPair<long> i){
	addEdge(i.getX(), i.getY());
}

template<class T>
inline void Graph<T>::toCompl(OrderedPair<long> i){
	delEdge(i.getX(), i.getY());
}

template<class T>
inline void Graph<T>::swapElement(OrderedPair<long> i){
	if(hasEdge(i.getX(), i.getY())) delEdge(i.getX(), i.getY());
	else addEdge(i.getX(), i.getY());
}

template<class T>
inline bool Graph<T>::isInSet(OrderedPair<long> i){
	return hasEdge(i.getX(), i.getY());
}

template<class T>
inline bool Graph<T>::isInCompl(OrderedPair<long> i){
	return !hasEdge(i.getX(), i.getY());
}

template<class T>
inline OrderedPair<long>* Graph<T>::toArray(long* size){
	*size = nedges();
	OrderedPair<long>* pairs = new OrderedPair<long>[*size];
	long sz = 0;
	for(long i = 0; i < n; i++){
		for(long j = 0; j < n; j++){
			if(hasEdge(i,j)){
				pairs[sz].setX(i);
				pairs[sz].setY(j++);
			}
		}
	}
	return pairs;
}

template<class T>
inline long Graph<T>::size(){
	return n;
}

template<class T>
inline void Graph<T>::allToSet(){
	for(long i; i < n; i++){
		adj[i]->allToSet();
	}
}

template<class T>
inline void Graph<T>::allToCompl(){
	for(long i; i < n; i++){
		adj[i]->allToCompl();
	}
}

template<class T>
inline OrderedPair<long> Graph<T>::firstInSet(){
	OrderedPair<long> pair(0,0);
	long x = 0;
	long y = adj[x]->nextSetElement(0);
	while(y >= n){
		x++;
		y = adj[x]->nextSetElement(0);
	}
	pair.setX(x);
	pair.setY(y);
}

template<class T>
inline OrderedPair<long> Graph<T>::firstInCompl(){
	OrderedPair<long> pair(0,0);
	long x = 0;
	long y = adj[x]->nextComplElement(0);
	while(y >= n){
		x++;
		y = adj[x]->nextComplElement(0);
	}
	pair.setX(x);
	pair.setY(y);
}

template<class T>
inline long Graph<T>::cardOfSet(){
	return nedges();
}

template<class T>
inline long Graph<T>::cardOfCompl(){
	return n*n - n - nedges();
}

template<class T>
inline void Graph<T>::setComplement(){
	complement();
}

template<class T>
inline void Graph<T>::setComplement(OrderedSet<OrderedPair<long> > * res){
	res = (OrderedSet<OrderedPair<long> > *)clone();
	res->setComplement();
}

template<class T>
inline void Graph<T>::show(){
	printf("numero de vértices = %lu \n", n);
	for(long i = 0; i < n; i++){
		printf("vértices %lu :\n", i);
		for(long j = 0; j < n; j++) if(hasEdge(i,j))printf("<%lu> ", j);
		printf("\n");
	}

}


#endif /* GRAPH_H_ */
